package com.zlk.algorithm.dataStructure.graph.topological;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

// 拓扑排序模版（Leetcode）
// 邻接表建图（动态方式）
// 课程表II
// 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1
// 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi]
// 表示在选修课程 ai 前 必须 先选修 bi
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1]
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序
// 你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组
// 测试链接 : https://leetcode.cn/problems/course-schedule-ii/
public class Code02_TopoSortDynamicLeetcode {

	@Test
	public void findOrder(){
		//findOrder(2,null);
		// [[1,0],[1,2],[0,1]]
		int [][] pre = new int[3][2];
		pre[0] = new int[]{1,0};
		pre[1] = new int[]{1,2};
		pre[2] = new int[]{0,1};
		findOrder(3,pre);
	}

	public static int[] findOrder(int numCourses, int[][] prerequisites) {
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		// 0 ~ n-1
		for (int i = 0; i < numCourses; i++) {
			graph.add(new ArrayList<>());
		}
		int[] indegrees = new int[numCourses];
		if(prerequisites!=null){
			for (int[] edge : prerequisites) {
				graph.get(edge[1]).add(edge[0]);
				indegrees[edge[0]]++;
			}
		}
		//利用队列
		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < indegrees.length; i++) {
			if(indegrees[i]==0){
				queue.add(i);
			}
		}

		int [] ans =new int[numCourses];
		int index = 0;
		while (!queue.isEmpty()){
			Integer cur = queue.poll();
			ans[index++]=cur;
			ArrayList<Integer> curList = graph.get(cur);
			for (Integer next : curList) {
				indegrees[next] = indegrees[next]-1;
				if(indegrees[next]==0){
					queue.add(next);
				}
			}
		}
		return index!=numCourses?new int[]{}:ans;
	}

}
